package pers.sloera.leetcode.editor.cn; /**
 * 给定一个二叉树的 根节点 root，请找出该二叉树的 最底层 最左边 节点的值。
 * <p>
 * 假设二叉树中至少有一个节点。
 * <p>
 * <p>
 * <p>
 * 示例 1:
 * <p>
 * <p>
 * <p>
 * <p>
 * 输入: root = [2,1,3]
 * 输出: 1
 * <p>
 * <p>
 * 示例 2:
 * <p>
 * <p>
 * <p>
 * <p>
 * 输入: [1,2,3,4,null,5,6,null,null,7]
 * 输出: 7
 * <p>
 * <p>
 * <p>
 * <p>
 * 提示:
 * <p>
 * <p>
 * 二叉树的节点个数的范围是 [1,10⁴]
 * -2³¹ <= Node.val <= 2³¹ - 1
 * <p>
 * Related Topics 树 深度优先搜索 广度优先搜索 二叉树 👍 338 👎 0
 */

//leetcode submit region begin(Prohibit modification and deletion)

import pers.sloera.leetcode.middle.TreeNode;

import java.util.Stack;

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 * int val;
 * TreeNode left;
 * TreeNode right;
 * TreeNode() {}
 * TreeNode(int val) { this.val = val; }
 * TreeNode(int val, TreeNode left, TreeNode right) {
 * this.val = val;
 * this.left = left;
 * this.right = right;
 * }
 * }
 */
// class Solution {
class Solution513 {
    public static void main(String[] args) {
        final Solution513 solution513 = new Solution513();
        solution513.findBottomLeftValue(new TreeNode(1, new TreeNode(2), new TreeNode(3)));
    }

    public int findBottomLeftValue(TreeNode root) {
        Stack<TreeNode> treeNodes = new Stack<>();
        treeNodes.add(root);
        int nodeCount = 1;
        TreeNode leftBottom = root;
        while (!treeNodes.empty()) {
            // 广度优先
            // 遍历上层所有的节点
            int currentLevelCount = 0;
            TreeNode leftCurrent = null;
            for (int i = 0; i < nodeCount; i++) {
                TreeNode node = treeNodes.pop();
                // System.out.println("node:"+node.val);
                if (node.left != null) {
                    // add 和 push 都是添加到了队尾。pop 即为队尾取
                    treeNodes.add(0, node.left);
                    currentLevelCount++;
                    if (leftCurrent == null) {
                        leftCurrent = node.left;
                    }
                }
                if (node.right != null) {
                    treeNodes.add(0, node.right);
                    currentLevelCount++;
                    if (leftCurrent == null) {
                        leftCurrent = node.right;
                    }
                }
            }
            // System.out.println("currentLevelCount:" + currentLevelCount);
            // System.out.println("treeNodes.size:" + treeNodes.size());
            // 同层的只取最左侧的
            if (leftCurrent != null) {
                // System.out.println("leftCurrent:" + leftCurrent.val);
                leftBottom = leftCurrent;
            }
            nodeCount = currentLevelCount;
        }
        return leftBottom.val;
    }
}
//leetcode submit region end(Prohibit modification and deletion)
